package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LeetCode5 {

    //暴力法 两个循环可以做
    //滑动窗口来做
    //滑动窗口感觉不对 滑动窗口适用于需要基于上一次的判断 比如是否有重复的数
//    public String longestPalindrome(String s) {
//        int length = s.length(), i = 0, j = 0, max = 0;
//        String result = "";
//        String r = new StringBuffer(s).reverse().toString();
//        while (i < length && j < length) {
//            if (s.substring(i, j).equals(r.substring(length - j - 1, length - i - 1))) {
//                j++;
//                if (j - i > max) {
//                    max = j - i;
//                    result = s.substring(i, j);
//                }
//            } else {
//                i = j + 1;
//                j = j + 1;
//            }
//        }
//        return result;
//    }

    //回文串的最大特点，正着和反着一样
    //o(n^2)
    //超出时间复杂度
    public String longestPalindrome1(String s) {
        int length = s.length(), max = 0;
        String r = new StringBuffer(s).reverse().toString();
        String result = "";
        for (int i = 0; i < length; i++) {
            for (int j = length - 1; j >= 0; j--) {
                if (j - i < max) {
                    break;
                }
                String substring = s.substring(i, j);
                if (substring.equals(r.substring(length - j, length - i))) {
                    if (j - i > max) {
                        max = j - i;
                        result = substring;
                    }
                    break;
                }
            }
        }
        return result;
    }

    public String longestPalindrome2(String s) {
        return null;
    }

//------------------------------------------------------------------

    public static void main(String[] args) {
        LeetCode5 leetCode5 = new LeetCode5();
        System.out.println(leetCode5.longestPalindrome("babad"));
//        System.out.println(leetCode5.isSymmetric(0,2,"babad"));
    }

    // o(n^3)
    public String longestPalindrome3(String s) {
        Map<Character, List<Integer>> dict = new HashMap<>();
        int maxLength = -1;
        String result = "";
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (dict.containsKey(c)) {
                dict.get(c).add(i);
            } else {
                List<Integer> list = new ArrayList<Integer>();
                list.add(i);
                dict.put(c, list);
            }
        }
        for (int startIndex = 0, endIndex = 0; startIndex < s.length(); startIndex++) {
            char c = s.charAt(startIndex);
            List<Integer> list = dict.get(c);
            for (int j = list.size() - 1; j >= 0; j--) {
                endIndex = list.get(j);
                if (endIndex - startIndex <= maxLength)
                    break;
                if (isSymmetric(startIndex, endIndex, s)) {
                    maxLength = endIndex - startIndex;
                    result = s.substring(startIndex, endIndex + 1);
                    break;
                }
            }
        }

        return result;
    }

    private boolean isSymmetric(int startIndex, int endIndex, String s) {
        if (startIndex > endIndex)
            return false;
        while (startIndex < endIndex) {
            if (s.charAt(startIndex) != s.charAt(endIndex))
                return false;
            startIndex++;
            endIndex--;
        }
        return true;
    }

    //------------------------------------------------------------------
    public String longestPalindrome5(String s) {
        if (s.length() < 2)
            return s;
        int maxLength = 1, startIndex = 0;
        boolean[][] dict = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            dict[i][i] = true;
        }

        for (int j = 1; j < s.length(); j++) {
            for (int i = 0; i < j; i++) {
                if (s.charAt(i) != s.charAt(j))
                    dict[i][j] = false;
                else {
                    if (j - i < 3)
                        dict[i][j] = true;
                    else
                        dict[i][j] = dict[i + 1][j - 1];
                }
                if (dict[i][j] && j - i + 1 > maxLength) {
                    maxLength = j - i + 1;
                    startIndex = i;
                }
            }
        }
        return s.substring(startIndex, startIndex + maxLength);
    }

    public String longestPalindrome(String s) {
        int maxLength = 0;
        String result = "";
        return null;
    }


}
